package com.my.code.sort;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * <b>基数排序</b><p>
 * 基数排序也是一种非比较排序算法，对数的每一位进行排序，从最低位开始
 *
 * @author zzl
 * @date 2020/10/19
 */
public class RadixSort {

    public static void main(String[] args) {
        int[] arr = {5, 7, 1, 6, 4, 8, 3, 2, 33, 22, 17, 13, 11};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void sort(int[] arr) {
        //1. 先算出最大数的位数
        int max = arr[0];
        for (int val : arr) {
            if (val > max) max = val;
        }

        int maxDigit = 0;
        while (max != 0) {
            max /= 10;
            maxDigit++;
        }

        //2. 按照10进制位数放入桶中
        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>(maxDigit);
        for (int i = 0; i < 10; i++) {//初始化每一位的list
            bucketList.add(new ArrayList<>());
        }

        int mod = 10, div = 1;
        for (int i = 0; i < maxDigit; i++, mod *= 10, div *= 10) {
            for (int val : arr) {
                int num = (val % mod) / div;
                bucketList.get(num).add(val);//个位入桶->百位入桶->千位
            }

            int index = 0;
            for (ArrayList<Integer> list : bucketList) {
                for (Integer val : list) {
                    arr[index++] = val;
                }
                list.clear();
            }
        }
    }

}
